package codingforgreat.lchot150;

import java.util.HashMap;
import java.util.PriorityQueue;

public class Lc347 {
    public class Node{
        public int val;
        public int count;
        public Node(int num){
            val = num;
            count = 1;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Node> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i],new Node(nums[i]));
            }else{
                map.get(nums[i]).count++;
            }
        }
        PriorityQueue<Node> queue = new PriorityQueue<>((a, b) ->{return a.count - b.count;});
        for(Node node : map.values()){
            if(queue.size() < k ||(queue.size() == k && node.count > queue.peek().count)){
                queue.add(node);
            }
            if(queue.size() > k){
                queue.poll();
            }
        }
        int[] ans = new int[k];
        int index = 0;
        while(!queue.isEmpty()){
            ans[index++] = queue.poll().val;
        }
        return ans;
    }
}
